//
//  XBGtoTExample.c
//  数据结构算法和笔试题
//
//  Created by 王国栋 on 16/6/23.
//  Copyright © 2016年 xiaobai. All rights reserved.
//

#include "XBGtoTExample.h"
#include <stdlib.h>


// 图的最小生成树 克鲁斯卡尔算法

struct edage
{
    int u;
    int v;
    int w;
};
static struct edage e[100];
static int f[100]={0};
static int sum=0,count=0;

//并查集
int getFF(int v)
{
    if (f[v]==v) {
        return v;
    }
    else
    {
        f[v]=getFF(f[v]);
        return f[v];
    }
    
}
int merge(int v,int u)
{
    v = getFF(f[v]);
    u = getFF(f[u]);
    if (v!=u) {
        
        f[u]=v;
        return 1;
    }
    return 0;
}

int cmp( const void *a , const void *b )

{
    
    struct edage *c = (struct edage *)a;
    struct edage *d = (struct edage *)b;
    return c->w - d->w;
}
void Kruskal()
{
    int n,m;//顶点数目和边的个数
    scanf("%d %d",&n,&m);
    for (int i=1; i<=m; i++) {
        
        scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
    }
    
    //核心算法 -- 克鲁斯卡尔

    qsort(e,m,sizeof(e[0]),cmp);//快速排序
    
    for (int i=1; i<=n; i++) {//初始化并查集
        
        f[i]=i;
    }
    for (int i =1; i<=m; i++) {
        
        if (merge(e[i].v, e[i].u)) {//利用并查集判断是否两点是否连通,这里表示本来是未连通的，现在连通了
            count++;
            sum+=e[i].w;
        }
        if (count==n-1) {//连接到n-1条边就可以停止了
            
            break;
        }
    }
    
    printf("%d",sum);

}


// --没写出来

//void Prim()
//{
//    int n,m;//顶点数目和边的个数
//    int inf = 999999999;
//    int cnt=0;
//    scanf("%d %d",&n,&m);
//    int book[n+1];
//    int ff[n+1];
//    for (int i = 1; i<=n; i++) {
//        
//        ff[i]=i;//初始化并查集
//    }
//    int dis[m+1];//存放的是1各个节点到1号节点的距离
//    for (int i=1; i<=m; i++) {
//        
//        scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
//        if (e[i].u==1||e[i].v==1) {
//            
//            dis[i]=e[i].w; //初始化dis数组
//        }
//        else
//        {
//            dis[i]= inf;
//        }
//    }
//    
//    book[1]=1;//1号节点已经加入
//    cnt++;
//    
//    //核心算法 -- 普利姆算法，dis保存的是未加入生成树的点到已经存在的最小生成树的距离
//    
////    for (int i = 1; i<=n-1; i++) {//n个节点，需要n-1个线就够了
////        
////        int u = 2,min = inf;
////        for (int k=2; k<=n; k++) {//这里是除了1号节点外的所有节点
////            //没有和一号顶点在一个集合中
////            if (getF(k)!=1&&dis[k]<min) {
////                
////                min = dis[k];
////                u = k;
////            }
////        }
////       // merge(e[1].u, e[1].v);
////        
////        
////    }
//    
//    int j;
//    int min = inf;
//    while (count<n) {
//        
//        min = inf;
//        for (int i =1; i<=n; i++) {
//            
//            if (book[i]==0&&dis[i]<min) {
//                
//                min = dis[i];
//                j = i;
//            }
//        }
//        book[j]=1;
//        count ++ ;
//        sum+=dis[j];
//        for (int k=1; k<=n; k++) {
//            
//            if (book[k]==0&&dis[k]>e[j].w) {
//                
//                dis[k]=e[j][k];
//            }
//        }
//    }
//    
//    
//    
//    printf("%d",sum);
//    
//}
//
//


void Prim()
{
    //这里貌似不适合用上面的把边做成结构体。不然访问的时候很难访问。
    int min,t1,t2,t3;
    int m,n;
    int e[7][7],dis[7],book[7]={0};
    int inf = 99999999;
    int cnt = 0;
    int sum = 0;
    scanf("%d %d",&n,&m);//n表示顶点的个数，m表示边的个数
    for (int i=1; i<=n; i++) {
        
        for (int j=1; j<=n; j++) {
            
            if (i==j) {
                
                e[i][j]=0;
            }
            else{
                e[i][j]=inf;
            }
        }
    }
    for (int i = 1; i<=m; i++) {
        
        scanf("%d %d %d",&t1,&t2,&t3);
        e[t1][t2]=t3;
        e[t2][t1]=t3;//这里是无向图
    }
    //初始化dis数组
    for (int i =1 ; i<=n; i++) {
        
        dis[i]=e[1][i];//存储一号顶点的到其他各个点的距离，开始存放的时候只有一个点
    }
    book[1]=1;
    count++;
    while (count<n) {//只要没有把所有的点加入dis数组
        min = inf;
        int u=1;
        for (int i = 1; i<=n; i++) {
            
            if (book[i]==0&&dis[i]<min) {
                
                u = i;
                min = e[1][i];
            }
        }
        book[u]=1;
        cnt++;
        sum+=dis[u];
        //扫描当前顶点u的所有边，以u为中间点更新生成树到每一个非树顶点的距离
        for (int k =1; k<=n; k++) {
            
//            if (dis[u]+e[u][k]<dis[k]) {
//                
//                dis[k]=dis[u]+e[u][k];
//            }
            if (book[k]==0&&dis[k]>e[u][k]) {//这里当时没有想到怎么表达
                
                dis[k]=e[u][k];
            }
        }
    }
    
    
}














